//给定两个单词 word1 和
// word2 ，返回使得
// word1 和 
// word2 相同所需的最小步数。 
//
// 每步 可以删除任意一个字符串中的一个字符。 
//
// 
//
// 示例 1： 
//
// 
//输入: word1 = "sea", word2 = "eat"
//输出: 2
//解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
// 
//
// 示例 2: 
//
// 
//输入：word1 = "leetcode", word2 = "etco"
//输出：4
// 
//
// 
//
// 提示： 
// 
//
// 
// 1 <= word1.length, word2.length <= 500 
// word1 和 word2 只包含小写英文字母 
// 
//
// Related Topics 字符串 动态规划 👍 636 👎 0

package leetcode.editor.cn;
//java:两个字符串的删除操作
public class Q0583DeleteOperationForTwoStrings {
    public static void main(String[] args){
        Solution solution = new Q0583DeleteOperationForTwoStrings().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word1.length() == 0 || word1.length() > 500) return -1;
        if (word2 == null || word2.length() == 0 || word2.length() > 500) return -1;

        String w1 = " " + word1, w2 = " " + word2;
        int n1 = w1.length(), n2 = w2.length();
        int[][] dp = new int[n1][n2];
        for (int i = 1; i < n1; i++) {
            for (int j = 1; j < n2; j++) {
                if (w1.charAt(i) == w2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return n1 + n2 - 2 * dp[n1 - 1][n2 - 1] - 2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}